package cn.guyouda.algorithms.sort;


/**
 * 快速排序
 *
 * @author Youda
 */
public class QuickSort {

    public static void sort(Comparable[] s, int lo, int hi) {

        if (lo >= hi) {
            return;
        }

        int j = partition(s, lo, hi); //拆分
        sort(s, lo, j - 1); //排序左半部分
        sort(s, j + 1, hi); //排序右半部分

    }


    /**
     * 拆分，左半部分小于v ,右半部分大于v v = s[lo];
     *
     * @param s
     * @param lo
     * @param hi
     * @return
     */
    public static int partition(Comparable[] s, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = s[lo];

        while (true) {
            while (less(s[++i], v)) {
                if (i == hi) {
                    break;
                }
            }

            while (less(v, s[--j])) {
                if (j == lo) {
                    break;
                }
            }

            if (i >= j) {
                break;
            }
            exchange(s, i, j);

        }
        exchange(s, lo, j);
        return j;
    }


    //比较x是否小于y
    public static boolean less(Comparable x, Comparable y) {
        return x.compareTo(y) < 0;
    }

    //交换 x,y
    public static void exchange(Comparable[] src, int x, int y) {
        Comparable z = src[x];
        src[x] = src[y];
        src[y] = z;
    }


    public static void main(String[] args) {

        //测试数据
        String[] src = {"a", "x", "z", "i", "y", "o", "l", "q", "b", "d", "z", "s", "c"};
        Integer[] src1 = {100, 99, 70, 98, 99, 101, 3, 6, 676, 45, 25, 77, 80, 1, 0, 46, 28, 11111, 56666, 22, 6, 8, 29};

        System.out.println("===========原数组==========");
        for (String str : src) {
            System.out.print(str + ",");
        }

        sort(src, 0, src.length - 1);//排序

        System.out.println();
        System.out.println("==========排序后==========");
        for (String str : src) {
            System.out.print(str + ",");
        }


        System.out.println();
        System.out.println("==========原数组=========");
        for (int i = 0; i < src1.length; i++) {
            System.out.print(src1[i] + ",");
        }

        sort(src1, 0, src1.length - 1);

        System.out.println();
        System.out.println("==========排序后==========");
        for (int i = 0; i < src1.length; i++) {
            System.out.print(src1[i] + ",");
        }

    }

}
